# source:https://leetcode.cn/problems/design-browser-history/ 
class BrowserHistory:

    def __init__(self, homepage: str):
        self.stack = [homepage]
        self.ptr = 0

    def visit(self, url: str) -> None:
        n = len(self.stack) - 1
        temp = n - self.ptr
        while temp > 0:
            self.stack.pop()
            temp -= 1
        self.stack.append(url)
        self.ptr = len(self.stack)-1
    def back(self, steps: int) -> str:
        print(self.stack)
        for _ in range(steps):
            if self.ptr > 0:
                self.ptr -= 1
        return self.stack[self.ptr]

    def forward(self, steps: int) -> str:
        print(self.stack)
        n = len(self.stack)
        for _ in range(steps):
            if self.ptr < n-1:
                self.ptr += 1
        return self.stack[self.ptr]

# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)

# source:https://leetcode.cn/problems/maximum-total-reward-using-operations-i/description/ 0-1背包问题
class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        rewardValues.sort()  # 先排序
        n = len(rewardValues)

        # 用字典存储状态，key = (i, x)，value = 最大奖励
        dp = [{} for _ in range(n+1)]
        dp[0][0] = 0  # 初始状态

        for i in range(1, n+1):  # 遍历所有元素
            for x in dp[i-1]:  # 遍历所有可能的 x
                # 不选 rewardValues[i-1]（继承上一个状态）
                dp[i][x] = dp[i-1][x]

                # 选 rewardValues[i-1]（前提是 rewardValues[i-1] > x）
                new_x = x + rewardValues[i-1]
                if rewardValues[i-1] > x:
                    dp[i][new_x] = dp[i-1][x] + rewardValues[i-1]

        return max(dp[n].values())